package weekthree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class NQueens_51 {
    private List<List<Integer>> ans;
    private boolean[] visited;
    private int length;
    private List<Integer> path;
    private Set<Integer> plusSet;
    private Set<Integer> minusSet;

    //DFS全排列模板 + queen的合法性检查
    //皇后的位置 1. i唯一；2， j唯一；3，i+j唯一；4， i-j唯一
    public List<List<String>> solveNQueens(int n) {
        ans = new ArrayList<>();
        plusSet = new HashSet<>();
        minusSet = new HashSet<>();
        length = n;
        visited = new boolean[length];
        path = new ArrayList<>();
        dfs(0);
        List<List<String>> res = new ArrayList<>();
        for(List per : ans){
            List<String> option = new ArrayList<>();
            for(int i=0;i<n;i++){
                StringBuilder sb = new StringBuilder();
                for(int j=0;j<n;j++){
                    if(j==(int)per.get(i)) sb.append("Q");
                    else sb.append(".");
                }
                option.add(sb.toString());
            }
            res.add(option);

        }
        return res;
    }

    //DFS全排列模板
    private void dfs(int index){
        if(index==length){
            ans.add(new ArrayList<>(path));
            return;
        }

        for(int i=0;i<length;i++){
            if(visited[i] || plusSet.contains(index+i) || minusSet.contains(index - i)) continue;
            visited[i]=true;
            plusSet.add(index+i);
            minusSet.add(index-i);
            path.add(i);
            dfs(index+1);
            visited[i]=false;
            path.remove(path.size()-1);
            plusSet.remove(index+i);
            minusSet.remove(index-i);
        }
    }
}
